package bit_operation;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description 剑指 Offer II 005. 单词长度的最大乘积
 * @Author Firenut
 * @Date 2023-04-16 18:21
 */
public class II005_maxProduct {
    // 如何判断两个字符串是否包含相同字符?
    // 思路:
    // 可通过位运算,将字符串的每个字符映射到32位的int上,通过01来标记该字符是否出现
    // 要映射到指定位置,可先让1进行左移,然后再与原先的int做一次或运算
    // 最后 两个字符串对应的二进制数进行与运算，如果结果为0，表示两个字符串不存在重复字符;否则字符串存在重复字符

    // 优化:
    // eg:对于字符串 ab aabb aaaaabbbbb，其对应的二进制标记位是一样的
    // 只需记录最长的字符串即可, 这样也可以减少比较的次数
    // 可使用 map, 记录二进制位与字符串长度的映射关系

    // 字符串个数: n; 字符串平均长度 : m
    // 时间复杂度：O((m + n)* n)
    // 空间复杂度：O(n) 需要创建一个map
    public int maxProduct(String[] words) {
        Map<Integer, Integer> map = new HashMap<>();
        // O(n*m)
        for (String word : words) {
            int bitMask = 0;
            for (char ch : word.toCharArray()) {
                int bit = 1 << ch - 'a';
                bitMask |= bit;
            }
            map.put(bitMask, Math.max(map.getOrDefault(bitMask, 0), word.length()));
        }

        int ans = 0;
        // O(n^2)
        for (Integer bitMask1 : map.keySet()) {
            for (Integer bitMask2 : map.keySet()) {
                if ((bitMask1 & bitMask2) == 0) {
                    ans = Math.max(ans, map.get(bitMask1) * map.get(bitMask2));
                }
            }
        }
        return ans;
    }
}
